import javax.xml.soap.Node;

/**
 * Created by cc
 * Description:
 * User: CZH
 * Date: 2022-09-15
 * Time: 9:42
 */
class ListNode {
    public int val;
    public ListNode next;//null

    public ListNode(int val) {
        this.val = val;
    }
}

public class MyLinkedList {
        public ListNode head;//标识单链表的头节点

        /**
         * 穷举的方式 创建链表  当然很low。此处只是为了好理解
         */
        public void createList() {
            ListNode listNode1 = new ListNode(12);
            ListNode listNode2 = new ListNode(3);
            ListNode listNode3 = new ListNode(5);
            ListNode listNode4 = new ListNode(2);
            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = listNode4;
            this.head = listNode1;
        }

        /**
         * 打印单链表
         */
        public void show() {
            ListNode cur = this.head;
            while (cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
            System.out.println();
        }

        //得到单链表的长度
        public int size() {
            int count = 0;
            ListNode cur = this.head;
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }

        //查找是否包含关键字key是否在单链表当中 15
        public boolean contains(int val) {
            ListNode cur = this.head;
            while (cur != null) {
                if (cur.val == val) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }



        //头插法
        public void addFirst(int data) {
           ListNode listNode = new ListNode(data);
            if (this.head == null) {
                this.head = listNode;
            }else {
                listNode.next = this.head;
                this.head = listNode;
            }
        }


        //尾插法
        public void addLast(int data) {
            ListNode listNode = new ListNode(data);
            if (this.head == null) {
                this.head = listNode;
            }else {
                ListNode cur = this.head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = listNode;
            }
        }


        //找链表的指定位置的前一位数据节点
        public ListNode searchPrev(int index) {
            int count = 0;
            ListNode cur = this.head;
            while (count != index-1) {
                cur = cur.next;
                count++;
            }
            return cur;//
        }

        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
            if (index < 0 || index > size()) {
                System.out.println("index位置不合法~");
                return;
            }
            if (index == 0) {
                addFirst(data);
                return;
            }
            if (index == size()) {
                addLast(data);
                return;
            }
            ListNode listNode = new ListNode(data);
            ListNode cur = searchPrev(index);
            listNode.next = cur.next;
            cur.next = listNode;
        }


        //找节点值为val的前一个节点
        public ListNode searchPrevNode(int val) {
            ListNode cur = this.head;
            //只要下一个节点的值不是null，就去找
            while (cur.next != null) {
                //值相等，就返回cur的前驱节点
                if (cur.next.val == val) {
                    return cur;
                }
                //不相等，就继续向后找
                cur = cur.next;
            }
            //跳出循环，没找到
            return null;
        }


        //删除第一次出现关键字为key的节点
        public void remove(int val) {
            if (this.head == null) return;
            //如果要删除的节点是头节点
            if (val == this.head.val) {
                this.head = this.head.next;
                return;
            }
            //待删除节点的前一个节点
            ListNode cur = searchPrevNode(val);
            if (cur == null) {
                System.out.println("没有你要删除的节点");
                return;
            }
            //要删除的节点
//            ListNode del = this.head;
            ListNode del = cur.next;
            //如果要删除的节点在中间
//            while (del.next != null){
//                if (del.val == val) {
//                    cur.next = del.next;
//                    del.next = null;
//                    return;
//                }
//                del = del.next;
//            }
            cur.next = del.next;

//            //如果要删除的节点在最后
//            cur.next = null;
        }


        //删除所有值为key的节点
        public void removeAllKey(int val) {
            if (this.head == null) return;
            //前驱节点
            ListNode prev = this.head;
            //判断节点
            ListNode cur = this.head.next;
            //判断节点不为空，进入循环
            while (cur != null) {
                //找到同数据节点删除
                if (cur.val == val) {
                    prev.next = cur.next;
                    //判断节点继续后移
                    cur = cur.next;
                }else { //节点数据不一样，向后找
                    //两个节点后移
                    prev = cur;
                    cur = cur.next;
                }
            }
            //最后判断头节点
            if (this.head.val == val) {
                this.head = this.head.next;
            }
        }


        public void clear(){
            while (this.head != null) {
                ListNode curNext = this.head.next;
                this.head.next = null;
                this.head = curNext;
            }
        }


    /**
     * 头插法处理链表逆序
     * @return
     */
    public ListNode reverseList() {
            if (this.head == null || this.head.next == null) {
                return this.head;
            }
            ListNode cur = this.head;
            ListNode newHead = null;
            while (cur != null) {
                //每次进入都先保存cur下一个新节点
                ListNode curNext = cur.next;
                //新节点将是上一个节点
                cur.next = newHead;
                //彼此交互
                newHead = cur;
                cur = curNext;
            }
            //要把新的头节点设置给head.
            //this.head = newHead;

            //最后是新链表的头结点.
            return newHead;
        }


        /**
         * 从指定位置开始打印链表
         * @param newHead
         */
        public void show2(ListNode newHead) {
            ListNode cur = newHead;
            while (cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
            System.out.println();
        }


        /**
         * 三指针法处理链表逆序
         * prev\cur\cur.next 三个引用相互协助
         * @return
         */
        public ListNode reverseList2() {
            ListNode prev = null;
            ListNode cur = this.head;
            ListNode newHead = null;
            while (cur != null) {
                ListNode curNext = cur.next;
                if (curNext == null) {
                    newHead = cur;
                }
                cur.next = prev;
                prev = cur;
                cur = curNext;
            }
            return newHead;
        }


    /**
     * 只走一遍，找出链表中的中间节点
     * @return
     */
    public ListNode middleNode() {
            if (this.head == null || this.head.next == null) {
                return this.head;
            }
            ListNode fast = this.head;
            ListNode slow = this.head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }


    /**
     * 找链表中倒数第k个节点
     * @param k
     * @return
     */
    public ListNode findKthToTail(int k) {
        if (k < 0) {
            return null;
        }
        //设置快慢节点.
        ListNode fast = this.head;
        ListNode slow = this.head;
        //先让fast节点先走.
        while (k-1 != 0) {
            //判断fast节点是否走超出了链表.
            if (fast.next != null) {
                fast = fast.next;
                k--;
            }else {
                return null;
            }
        }
        //一起走，fast到终点，slow位置就是倒数第k个节点.
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    //返回倒数k个节点，方法二.
    public ListNode findKthToTail2(int k) {
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null) {
            if (k <= 0) {
                slow = slow.next;
            }
            fast = fast.next;
            k--;
        }
        return k <= 0 ? slow : null;
    }


    /**
     * 拼接两个有序的链表
     * @param headA
     * @param headB
     * @return
     */
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        if (headA == null && headB == null) return null;
        if (headA == null)  return headB;
        if (headB == null)  return headA;

        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;

        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
            }else {
                tmp.next = headB;
                headB = headB.next;
            }
            tmp = tmp.next;
        }

        if (headA == null)
            tmp.next = headB;
        if (headB == null)
            tmp.next = headA;

        return newHead.next;
    }



        public ListNode partition( int x) {

            ListNode cur = this.head;
            ListNode bs = null;
            ListNode be = null;
            ListNode as = null;
            ListNode ae = null;

            while(cur != null) {
                if(cur.val < x) {
                    //第一次插入
                    if(bs == null) {
                        bs = cur;
                        be = cur;
                    }else {
                        be.next = cur;
                        be = be.next;
                    }
                }else {
                    //第二部分第一次插入
                    if(as == null) {
                        as = cur;
                        ae = cur;
                    }else {
                        ae.next = cur;
                        ae = ae.next;
                    }
                }
                cur = cur.next;
            }
        /*if(bs == null) {
            return as;
        }else {
            be.next = as;
            ae.next = null;//注意问题，ae可能为空
            return bs;
        }*/
            if(bs == null) {
                return as;
            }
            //bs!=null
            be.next = as;
            if(as != null) {
                ae.next = null;
            }
            return bs;
        }

        public ListNode deleteDuplication() {

            ListNode newHead = new ListNode(-1);
            ListNode tmp = newHead;
            ListNode cur = this.head;
            while (cur != null) {
                //cur.next != null : 判断是不是只有一个节点 或者 是不是尾巴节点
                if(cur.next != null && cur.val == cur.next.val) {
                    //cur再走的过程当中，有可能剩下的都是相同的
                    while ( cur.next != null && cur.val == cur.next.val) {
                        cur = cur.next;
                    }
                    cur = cur.next;//多走一步
                }else {
                    tmp.next = cur;
                    tmp = tmp.next;
                    cur = cur.next;
                }
            }
            tmp.next = null;//手动设置，防止最后一个节点是重复的
            return newHead.next;
        }

        public boolean chkPalindrome() {
            if(this.head == null) {
                return true;
            }
            if(this.head.next == null) {
                //只有一个节点
                return true;
            }
            //1、找中间节点
            ListNode slow = this.head;
            ListNode fast = this.head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            //slow 指向的节点 就是中间节点
            //2、进行翻转
            ListNode cur = slow.next;
            while (cur != null) {
                ListNode curNext = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            //翻转完毕 slow指的地方就是 最后一个节点
            while (slow != head) {
                if(slow.val != head.val) {
                    return false;
                }
                if(head.next == slow) {
                    return true;
                }
                head = head.next;
                slow = slow.next;
            }
            return true;
        }

        public boolean hasCycle1() {
            ListNode fast = this.head;
            ListNode slow = this.head;

            while(fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if(slow == fast) {
                    return true;
                }
            }
            return false;
        }

        public void createCycle() {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            //cur.next == null
            cur.next = this.head.next;
        }

        public boolean hasCycle() {
            ListNode fast = this.head;
            ListNode slow = this.head;

            while(fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if(slow == fast) {
                    break;
                }
            }
            if(fast == null || fast.next == null) {
                return false;
            }
            return true;
        }

        public ListNode detectCycle() {
            ListNode fast = this.head;
            ListNode slow = this.head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (slow == fast) {
                    break;
                }
            }

            if(fast == null || fast.next == null) {
                return null;
            }

            //x == y
            slow = this.head;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow;

            //x == c(n-1) + y

        }




}
